1. Field of the Invention
This invention relates to computer-aided design of digital electronic circuits, and more specifically to logic synthesis systems that start with a digital circuit model described in technology-independent terms and automatically generate a logically equivalent circuit model efficiently implemented in terms of a selected device technology.
2. Discussion of Related Art
Logic synthesis systems help reduce the time needed to design digital electronic circuits. Such systems allow designers to express the function of a circuit in logical technology-independent terms; for example, in terms of ANDs, ORs and inverters with unlimited fan-in and fan-out. Such a technology-independent design may include certain redundancies or other inefficiencies that make the design easier to develop and understand. After verification of logical features, the logic synthesis system is then employed to convert this technology-independent design into an optimized technology-specific design that incorporates rules and constraints for a specific digital technology; for example, MOSFET or bipolar technology. Such constraints may dictate the exclusive use of NOR gates with limited fan-in and fan-out, for instance. U.S. Pat. No. 4,703,435 assigned to the assignee hereof describes a logic synthesis system and is entirely incorporated herein by this reference.
The technology-specific output of such a logic synthesis system is further manipulated according to the rules of the selected device technology to yield a final manufacturable circuit design. This further device-specific design work may include such things as laying out the technology-dependent logic elements in an integrated circuit, routing interconnections between these elements, and verifying compliance with device-specific timing constraints. Thus, determining correspondence between signals in the original technology-independence model, signals in the intermediate technology-dependent model and signals in the final circuit layout is generally not possible except at specific boundaries.
After finishing this final device-specific design layout work, logical changes may be made to the original technology-independent model, either to correct errors or to introduce improvements. When this occurs, the logic synthesis system is again employed to generate a new intermediate technology-dependent model from the amended technology-independent model. This redesign is time-consuming. It may also introduce so many changes into the new intermediate technology-dependent design that much of the additional device-specific design work must also be repeated, consuming even more time.
Under many circumstances, the inability to fully relate the internal nodes in the resultant device-specific logic with those in the initial technology-independent logic is not a concern. If the resultant logic satisfies the area and speed criteria of the design and if it performs the required function, the internal signals are not closely evaluated. Automatic Boolean verification can be performed at the boundaries of the two logic models to confirm that they perform identical functions This may be done in any useful manner, such as with the method described by G. L. Smith, et al ("Boolean Comparison of Hardware and Flowcharts", IBM Journal of Research and Developement, Vol 26, No. 1, pp. 106-116 (1982)). This verification task can become difficult when the two models are large but difficulties can be minimized by selecting a small number of internal nodes as pseudo-boundary points for use during the verification process.
The changes made during reoptimization of large logic models are too pervasive to permit practical recovery of a change history. Some optimization techniques known in the art may inhibit the use of such history data even if they were available. Also, the global effects of logic changes can drastically alter logic that is seemingly unrelated to the region of the change. These global effects make impossible the reconstruction of a correspondence between the unchanged final device-specific model and the revised final device-specific model. Such global effects are also sometimes undesirable to a designer who, having already analyzed the unchanged portion of the final device-specific design, is satisfied with the results and does not wish those results altered.
Limiting the scope and influence of logic optimization by partitioning appears to be a simple and effective solution to this problem. This increases the likelihood for finding correspondence and isolating changes. Such is the approach taken by mapping systems that make only trivial changes to the model as necessary to meet the technology-specific rules or to eliminate unused circuits. The mapping approach actually diminishes the value of automated logic synthesis and burdens the logic designer with additional manual tasks needed to meet device area and speed constraints. Thus, the mapping method trades one error-prone manual task for another.
Practitioners have tried manually partitioning the technology-independent model into sections that are independently processed by a logic synthesizer. When a change is then made in the technology-independent model, only those partitions affected by the change need be resynthesized. However, the economy achieved by such manual partitioning is limited. If the partitions are small, they become difficult to manage, and a number of them may need to be changed. If they are large, any small change requires resynthesis of a large piece of logic, consuming inordinate time.
In U.S. Pat. No. 4,612,618, Richard L. Pryor, et al discusses a hierarchical technique for designing logic from the bottom up. They use repeated synthesis, first building a basic set of logical cells and then connecting these basic cells to form increasingly complex logic assemblies. Pryor, et al teach a form of logical partitioning, employing automated computer-aided techniques. While their partitioning method can limit the scope of logic revisions at the device-specific engineering level, they do not suggest how to select optimal partitioning in every situation.
A need thus exists in the art for a logic synthesis system that, having already once translated an earlier technology-independent model to technology-dependent form, can resynthesize an amended version of that technology-independent model to provide only the minimally necessary changes to the technology-dependent model. A logic synthesis system that functions in this fashion is generally denominated an "incremental" logic synthesis system.
In U.S. Pat. No. 4,882,690, Shinsha, et al discloses an incremental logic synthesis system. Their system performs a second synthesis of the entire amended technology-independent model and then compares the old and new technology-dependent models. The second synthesis is costly because it is applied to the full model. Also, sophisticated synthesis procedures that can delete signals may propagate a small change to the technology-independent model into major changes in the resulting technology-dependent model. In such case, later comparison of old and new technology-dependent versions reveals more changes than were made to the original technology-independent model. Shinsha, et al do not offer a method that preserves as much existing device-specific design work as possible without multiplying logical revisions into larger numbers of circuit changes.
In U.S. Pat. No. 5,003,487, Anthony E. Drumre, et al discloses a technique for correcting timing problems early in the logic synthesis process, thereby minimizing the effort otherwise later required. The problem solved by Drumm, et al is an example of why the simple incremental logic synthesis method of Shinsha, et al is not generally productive.
The Shinsha, et al incremental synthesis technique requires resynthesis of the entire logic model upon any modification however slight. Their merge procedure for combining revisions with the original model precedes their resynthesis of the new model, inviting the undesirable propagation of global effects discussed above. Their incremental synthesis method is not practical for use with very complex logic designs because it relies heavily on logical structure, which may not survive a sophisticated logic synthesis process. The Shinsha, et al approach to incremental logic synthesis also relies on the use of a mapping system rather than a full logic synthesis system so movement of signals forward or backward in the logic can jeopardize their resynthesis strategy as can removal of redundant or unnecessary signals. Also, their verification procedure requires rigorous point-by-point comparison of both the original and revised models regardless of the size or scope of the change.
Accordingly, there is a clearly felt need in the art for a logic synthesis system that can limit resynthesis to the logic in the vicinity of a change, thereby preserving the larger portion of the final device-specific design information already developed from the original intermediate technology-specific model. The related unresolved problems and deficiencies are clearly felt in the art and are solved by this invention in the manner described below.